Today’s Agenda

  • Our motivation
  • Hausmann’s curious question
  • Latschev’s remarkable (but qualitative!) answer
  • Finite reconstruction problem
  • Quantitative Latschev’s theorem
    • abstract manifolds
    • Euclidean submanifolds
  • Extension to CAT(κ)\mathrm{CAT}(\kappa) Spaces
  • Questions

The Vietoris–Rips Complexes

  • a metric space (X,dX)(X,d_X)

  • a scale β>0\beta>0

  • ℛβ(X)\mathcal{R}_\beta(X) is an abstract simplicial complex

    • XX is the vertex set
    • each subset A⊂XA\subset X of (k+1)(k+1) points with diameter at most β\beta is a kk-simplex.

Point Cloud

A sample

Learn Topological and Geometric Features

A Reconstruction

  • The topology is the wedge of two circles (two 11-dimensional cycles)
  • The geometry is graph-like

Good Shapes

Circle

Donut
  • Abstract Riemannian manifolds
  • Submanifolds of ℝN\mathbb{R}^N

Bad Shapes

Source: Kyoto City Official Traval Guide

A Real Application

The City of Berlin

Q: How to draw the map of the city from a noisy point-cloud of GPS locations?

A Reconstruction of Berlin

Source: mapconstruction.org

Reconstruction Goals

  • Goal: Infer the topology of MM from XX.

    • Estimate only the Betti numbers—number of connected components, cycles, voids, etc—of MM.

    • construct a topological space M̃\widetilde{M} from XX to retain the topology of MM, i.e., M≃M̃M\simeq\widetilde{M} in some appropriate sense.

      • homotopy equivalent
      • homeomorphic
      • geometrically close

The Theme of the Research

  • Provide a window of resolutions or scales for the Vietoris–Rips complexes for a topologically-faithful reconstruction

  • Design provable reconstruction algorithms particularly for bad shapes

  • Reconstruction under different noise models, e.g. the Gromov–Hausdorff distance

  • Probabilistic guarantees in the face of random samples

  • Understand the topology of ℛβ(X)\mathcal{R}_\beta(X)

  • When is the homology of ℛβ(X)\mathcal{R}_\beta(X) finitely generated?

  • Alternative to the Nerve Lemma for Vietoris–Rips complexes

  • Implications in Shape Reconstruction

Gromov’s Perspective

—Metric structures of Riemann & non-Riemann Spaces, page100

Let XX be a length metric space…given by ε\varepsilon-nets Xε0X_\varepsilon^{0} in XX which Hausdorff converges XX…

…One can turn such a space into a path metric space, namely a graph Xε1⊂XX_\varepsilon^{1}\subset X with Xε0X_\varepsilon^{0} as its vertex set, and where two points xx and yy in Xε1X_\varepsilon^{1} within distance δ≤δε\delta\leq\delta_\varepsilon joined by an edge of length δ\delta.

…fll in the small triangles of edges in the graph Xε1X_\varepsilon^{1} by actual 22-dimensional triangles to obtain Xε2⊂XX_\varepsilon^{2}\subset X, then π1(Xε2)=π1(X)\pi_1(X_\varepsilon^{2})=\pi_1(X) for ε,δε→0\varepsilon,\delta_\varepsilon\to0 with ε/δε→∞\varepsilon/\delta_\varepsilon\to\infty.

Hausmann’s Theorem

Hausmann (1995)

For any closed Riemannian manifold MM and 0<β<ρ(M)0<\beta<\rho(M), the Vietoris–Rips complex ℛβ(M)\mathcal{R}_\beta(M) is homotopy equivalent to MM.

  • Convexity Radius: ρ(M)\rho(M) is the largest (sup) radius so that geodesic balls are convex.
    • ρ(S1)=π2\rho(S^1)=\frac{\pi}{2}
    • ρ(M)>0\rho(M)>0 for a compact manifold
  • Hausmann constructed a homotopy equivalence T:ℛβ(M)→MT:\mathcal{R}_{\beta}(M)\to M
  • Since MM has finitely generated homology, so does ℛβ(M)\mathcal{R}_{\beta}(M)
  • vertex set is the entire manifold MM!

Finite Reconstruction Problem

Hausmann’s Curious Question

What about the Vietoris–Rips complex of a finite, dense subset S⊂MS\subset M?

  • Manifold reconstruction from a dense sample
  • More generally, a metric space (S,dS)(S,d_S) close to MM in the Gromov-Hausdorff distance.

Gromov–Hausdorff Distance:

  • similarity measure between abstract metric spaces (X,dX)(X,d_X) and (Y,dY)(Y,d_Y)
  • Definition: dGH(X,Y)=infdHZ(f(X),g(Y))d_{GH(X,Y)}=\inf d_H^Z(f(X),g(Y))
    • inf over metric spaces (Z,dZ)(Z,d_Z) and isometries f:X→Zf:X\to Z, g:Y→Zg:Y\to Z

Latschev’s Remarkable Solution

Latschev (2001)

Every closed Riemannian manifold MM has an ϵ0>0\epsilon_0>0 such that for any 0<β≤ϵ00<\beta\leq\epsilon_0 there exists some δ>0\delta>0 so that for any sample SS: dGH(S,M)≤δ⟹ℛβ(S)≃M. d_{GH}(S,M)\leq\delta\implies \mathcal R_\beta(S)\simeq M.

  • the threshold ϵ0=ϵ0(M)\epsilon_0=\epsilon_0(M) depends solely on the geometry of MM. But the theorem did not say how!

  • δ=δ(β)\delta=\delta(\beta) is a function (a fraction in practice) of β\beta.

  • The result is qualitative

    • it’s unavoidable (uses Lebesgue’s number lemma)

  • Nonetheless, the result provides a promising answer to Hausmann’s question, and more!

Quantitative Latschev’s Theorem

Metric Graph Reconstruction [J. Appl. & Comp. Top., Majhi (2023)]

Let (G,dG)(G,d_G) be a compact, path-connected metric graph, (S,dS)(S,d_S) a metric space, and β>0\beta>0 a number such that 3dGH(G,S)<β<34ρ(G).3d_{GH}(G,S)<\beta<\frac{3}{4}\rho(G). Then, ℛβ(S)≃G\mathcal R_\beta(S)\simeq G

  • The result is quantitative

    • ϵ0=34ρ(G)\epsilon_0=\frac{3}{4}\rho(G)

    • δ=13β\delta=\frac{1}{3}\beta

  • The constants are not optimal!

    • Optimal ϵ0=23ρ(G)\epsilon_0=\frac{2}{3}\rho(G).

Quantitative Latschev’s Theorem

Riemannian Manifold Reconstruction [SoCG’24, DCG, Majhi (2024)]

Let MM be a closed, connected Riemannian manifold. Let (S,dS)(S,d_S) be a compact metric space and β>0\beta>0 a number such that 1ξdGH(M,S)<β<11+2ξmin{ρ(M),π4κ} \frac{1}{\xi}d_{GH}(M,S)<\beta<\frac{1}{1+2\xi}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\} for some 0<ξ≤1/140<\xi\leq1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.

  • κ\kappa is an upper bound on the sectional curvatures of MM

  • For ξ=114\xi=\frac{1}{14}:

    • ϵ0=78min{ρ(M),π4κ}\epsilon_0=\frac{7}{8}\min\left\{\rho(M),\frac{\pi}{4\sqrt{\kappa}}\right\}

    • δ=β14\delta=\frac{\beta}{14}

Quantitative Latschev’s Theorem

Euclidean Submanifold Reconstruction (Majhi 2024)

Let M⊂ℝNM\subset\mathbb R^N be a closed, connected submanifold. Let S⊂ℝNS\subset\mathbb R^N be a compact subset and β>0\beta>0 a number such that 1ξdH(M,S)<β<3(1+2ξ)(1−14ξ)8(1−2ξ)2τ(M) \frac{1}{\xi}d_{H}(M,S)<\beta<\frac{3(1+2\xi)(1-14\xi)}{8(1-2\xi)^2}\tau(M) for some 0<ξ<1/140<\xi<1/14. Then, ℛβ(S)≃M\mathcal R_\beta(S)\simeq M.

  • τ(M)\tau(M) is the reach of MM

  • For ξ=128\xi=\frac{1}{28}:

    • ϵ0=3151352τ(M)\epsilon_0=\frac{315}{1352}\tau(M)

    • δ=β28\delta=\frac{\beta}{28}

Reach

Challenges

  • Bad spaces are ubiquitous in applications
    • manifolds with boundary or not a topological manifold
    • stratefied manifolds
    • Euclidean subsets with vanishing reach (due to corners)
    • A single Rips complex fails to be topologicall faithful, no matter the sample density
  • Challenges in extending Latschev’s theorem
    • defining convexity radius and sectional curvatures beyond closed Riemannian manifolds?
    • extending Jung’s theorem

Bounded Curvature Spaces

  • Length space: A metric space with an instrinsic metric
  • Geodesically complete: a pair can be joined by a length-minimizing path
  • CAT(κ)\mathrm{CAT}(\kappa): geodesic triangles are “slimmer” than corresponding “model triangles” in a standard space of constant curvature κ\kappa.
  • Examples:
    • Closed Riemannian manifolds
    • Submanifolds of ℝN\mathbb{R}^N
    • stratefied manifolds
    • metric graphs
    • embedded graphs in ℝN\mathbb{R}^N
    • Euclidean Polytopes
  • Lastchev’s Theorem for CAT(κ)\mathrm{CAT}(\kappa) Spaces (Komendarczyk, Majhi, and Tran 2024)

Euclidean Subset Reconstruction

  • The sample SS comes equipped with ∥⋅∥\|\cdot\|
  • Euclidean Vietoric–Rips ℛβ(S)\mathcal{R}_\beta(S) fails almost aways for any scale β\beta
  • Remedy?

ε\varepsilon-path Metric:

  • Fix an ε>0\varepsilon>0, proportional to dH(S,X)d_H(S,X)

  • For any two sample points a,b∈Sa,b\in S, define dSε(a,b)d_S^\varepsilon(a,b) to be the shortest distance when hopping over the points of SS with a step size of ε\varepsilon.

ε\varepsilon-path Metric on SS
  • For a dense enough sample SS of XX, dSεd^\varepsilon_S is quasi-isometric to the length metric on XX
  • Consider the Vietoris–Rips of SS under dεd_\varepsilon; call it ℛβε(S)\mathcal{R}_\beta^\varepsilon(S)

Euclidean Subsets (Komendarczyk, Majhi, and Tran 2024)

Let XX be a geodesic subspace of ℝN\mathbb R^N. Let ξ∈(0,1)\xi\in\left(0,1\right) and β>0\beta>0 be fixed numbers. 0<ε≤β0<\varepsilon\leq\beta such that δβε(X)≤1+(ξ1+ξ)\delta^\varepsilon_{\beta}(X)\leq1+\left(\frac{\xi}{1+\xi}\right), then for any compact subset S⊂ℝNS\subset\mathbb R^N with dH(X,S)<12ξεd_H(X,S)<\frac{1}{2}\xi\varepsilon, we have ℛβε(S)≃X\mathcal{R}_\beta^\varepsilon(S)\simeq X.

Back to Gromov